package com.cty.twentyThirdDay;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/*
 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

你的代码 只 接受原链表的头节点 head 作为传入参数。
* */
public class Q_32 {

    // 暴力解法 主包自己写的过了 时间复杂度O(L) 空间复杂度O(L) 因为用了一个ArrayList来记录每个节点的random节点位置L为链表的长度
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        // 先记录原链表的readom节点的index 如果是空就加入-1
        ArrayList<Integer> index = new ArrayList<>();
        Node cur = head;
        while (cur != null) {
            Node random = cur.random;
            if (random == null) {
                index.add(-1);
                cur = cur.next;
            } else {
                Node temp = head;
                int i = 1;
                while (temp != random) {
                    i++;
                    temp = temp.next;
                }
                // 记录原链表的index
                index.add(i);
                cur = cur.next;
            }
        }
        // 创建一个新链表
        Node newHead = new Node(head.val);
        // 令cur等于原链表的头部
        cur = head.next;
        // 构造新链表 没有random
        Node temp = newHead;
        while (cur != null) {
            temp.next = new Node(cur.val);
            temp = temp.next;
            cur = cur.next;
        }
        // 构造好之后开始构造random
        int i = 0;
        cur = newHead;

        while (cur != null) {
            // 获得cur的random节点索引
            int randomIndex = index.get(i);
            if (randomIndex == -1) {
                cur.random = null;
                cur = cur.next;
                i++;
                continue;
            }
            temp = newHead;
            for (int j = 0; j < randomIndex - 1; j++) {
                temp = temp.next;
            }
            cur.random = temp;
            i++;
            cur = cur.next;
        }
        return newHead;
    }

    // 力扣官方题解 方法一:回溯+哈希表
    /*
     * 思路:首先用一个哈希表来记录当前节点是否被复制 如果被复杂就直接返回
     *   没有被复制 复制之后存入 哈希表中 然后递归的先创建当前节点的下一个节点
     *   此时的全部节点已经被创建完 在递归的将当前节点的random节点做指向即可
     *   不用在创建节点
     *   时间复杂度O(n) 空间复杂度O(n)
     * */

    public HashMap<Node, Node> map = new HashMap();

    public Node copyRandomList2(Node head) {
        if (head == null) {
            return null;
        }
        // 判断哈希表中的是否含有该节点 有则证明该节点已经被复制 没有则没有被复制 就复制
        if (!map.containsKey(head)) {// 节点没有被复制
            // 复制节点
            Node newHead = new Node(head.val);
            // 节点存入哈希表 表示已经被复制
            map.put(head, newHead);
            // 递归的创建下一个节点
            newHead.next = copyRandomList2(head.next);
            // 递归的创建下一个节点的random节点 当上一行代码进行最后一次递归时 也就是这一轮递归的开始 这时所有的节点已经都被创建 我们只做指向即可
            newHead.random = copyRandomList2(head.random);
        }
        // 返回创建的新节点
        return map.get(head);
    }

    // 力扣官方题解 迭代+节点拆分
    /*
     * 思路:
     *   就是将原链表的每一个节点后加一个节点 新增的节点与前一个节点的值相等 即为复制的节点
     *   然后加完之后 再将新增的节点的random节点 复制前一个节点的random节点 最后将节点断开即可
     *   时间复杂度O(L) 空间复杂度O(1) L是链表的长度
     * */
    public Node copyRandomList3(Node head) {
        if (head == null) {
            return null;
        }
        // 先新增下一个节点 注意:这里的node节点要走两步 因为复制后的多了一个节点
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = new Node(node.val);
            // 复制节点 放在每个节点的后面
            newNode.next = node.next;
            node.next = newNode;
        }
        // 开始复制random节点
        for (Node node = head; node != null; node = node.next.next) {
           Node newNode = node.next;
           // 如果当前节点不等于null 那就指向当前节点random节点的下一个节点(即复制的当前节点的random节点)
           newNode.random = (node.random != null)? node.random.next:null;
        }

        // 将链表断开
        // 记录新链表的头节点
        Node newHead = head.next;
        // 注意:因为是断开指针 node走一步即可 因为遍历过后 node就会指向原来的节点
        for (Node node = head; node != null; node = node.next) {
            // 先记录下下一个节点
            Node newNode = node.next;
            // 将当前节点的指向改变
            node.next = node.next.next;
            // 改变新节点的指向 注意:在这条代码还没执行前 newHead.next 的指向还没有变 所以还是指向的原链表的节点
            newNode.next = (newNode.next != null) ? newNode.next.next:null;
        }
        return newHead;
    }

}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
